Cerca vs decisió
Demostreu les conseqüències següents de la hipòtesi \mathsf{P} = \mathsf{NP}.
Existeix un algorisme de temps polinòmic que produeix un model (una assignació que satisfà la fórmula) quan se li dóna una fórmula booleana satisfactible.
Els enters es poden factoritzar en temps polinòmic.
Hi ha un algorisme de temps polinòmic que pren com a entrada un graf no dirigit i troba una clica màxima (vegeu l’exercici 7.2) continguda en aquest graf.
Els algorismes que se us demana proporcionar calculen una funció, però \mathsf{NP} conté llenguatges, no funcions. L’assumpció \mathsf{P} = \mathsf{NP} implica que decidir satisfactibilitat, no primalitat i l’existència de cliques d’una mida donada és resoluble en temps polinòmic. Però, encara que l’assumpció no mostra com trobar les solucions, heu de demostrar que es poden trobar igualment.